//无头单向非循环链表实现

public class SingleList {
    /*
    结点内部类
     */
    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head; //不初始化，默认就是null

    // 1 创建一个单链表
    public void createList(){
        ListNode listNode1 = new ListNode(11);
        ListNode listNode2 = new ListNode(22);
        ListNode listNode3 = new ListNode(33);
        ListNode listNode4 = new ListNode(44);
        ListNode listNode5 = new ListNode(55);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        this.head = listNode1; //设置一个头节点
    }

    // 2 打印单链表数据，默认从头开始打印
    public void display(){
        ListNode cur = this.head;
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    // 3 得到单链表的长度
    public int size(){
        int count = 0;
        ListNode cur = this.head;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    // 5 查找是否包含关键字key是否在单链表中
    public boolean contains(int key){
        ListNode cur = this.head;
        while (cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 6 头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        node.next = head;
        head = node;
    }

    // 7 尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);
        ListNode cur = this.head;
        //（1）如果是空链表，直接在头插入
        if(cur == null){
            this.head = node;
        }else { //（2）从最后边插入
            while (cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    // 8 任意位置插入，第一个数据节点为0号下标
    public void addIndex(int index, int data){
        if(index < 0 || index > size()){
            System.out.println("index位置不合法！");
            throw new IndexWrongfunException("index位置不合法！");
        }
        if(index == 0){
            addFirst(data);
            return;
        }
        if(index == size()){
            addLast(data);
            return;
        }
        //1)先走index-1步，找到cur
        ListNode cur = findIndexSubOne(index);
        ListNode node = new ListNode(data);
        //2)修改指向
        node.next = cur.next;
        cur.next = node;
    }

    private ListNode findIndexSubOne(int index){
        ListNode cur = this.head;
        while (index-1 != 0){
            cur = cur.next;
            index--;
        }
        return cur;
    }

    // 9 删除第一次出现关键字为key的节点
    public void remove(int key){
        if(this.head == null){
            return;
        }
        //删除头节点
        if(this.head.val == key){
            this.head = this.head.next;
            return;
        }

        ListNode cur = findPreOfKey(key);
        if(cur == null){
            System.out.println("没有你要删除的数字！");
            return;
        }
        ListNode del = cur.next;
        cur.next = del.next;
    }
    private ListNode findPreOfKey(int key){
        ListNode cur = this.head;
        while (cur.next != null){
            if(cur.next.val == key){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    // 10 删除所有值为key的结点
    public void removeAllKey(int key){
        if(this.head == null){
            return;
        }
        ListNode pre = this.head;
        ListNode cur = this.head.next;
        while (cur != null){
            if(cur.val == key){
                pre.next = cur.next;
                cur = cur.next;
            }else { //如果没找到key，则继续向后遍历
                pre = cur;
                cur = cur.next;
            }
        }
        if(this.head.val == key){ //如果要删除的是头节点
            this.head = this.head.next;
        }
    }

    // 11 清空单链表
    public void clear(){
        this.head = null;
    }

    //-----------------Oj题-----------------------
    /** eg2--  141. 环形链表 给你一个链表的头节点 head ，判断链表中是否有环。
     如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
     为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
     */
    public boolean hasCycle(){ //判断是否有环
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
    public void createLoop(){ //创建环
        ListNode cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        cur.next = head.next.next; //随便给定一个节点可以形成环
    }

    /** eg3 -- 142. 环形链表 II
     *  给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回null。
     */
    public ListNode detectCycle() {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){ //此时已经找到了环
                //开始找环的入口
                slow = head;
                while(fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }
        return null;
    }

    /** eg4
     * CM11 链表分割
     * @param pHead 头节点
     * @param x
     * @return
     */
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode as = null;
        ListNode ae = null;
        ListNode bs = null;
        ListNode be = null;
        ListNode cur = pHead;
        while(cur != null){
            if(cur.val < x){ //小于x的结点全部放在a链表中
                if(as == null){ //第一次插入将ae和as都赋值cur
                    as = cur;
                    ae = cur;
                }else{ //不是第一次插入，只将ae向后移动
                    ae.next = cur;
                    ae = ae.next;
                }
            }else{
                if(bs == null){ //第一次插入将be和bs都赋值cur
                    bs = cur;
                    be = cur;
                }else{ //不是第一次插入，只将be向后移动
                    be.next = cur;
                    be = be.next;
                }
            }
            cur = cur.next;
        } //遍历完成
        if(as == null){ //如果没有小于x的结点，直接返回大于x的一端节点bs
            return bs;
        }
        ae.next = bs;
        //如果大节点的一段最后一个节点没有指向空则需要手动置为null
        if(be != null){
            be.next = null;
        }
        return as;
    }

    /** eg5 -- 160. 相交链表
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pl = headA;
        ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;
        while(pl != null){
            pl = pl.next;
            lenA++;
        }
        while(ps != null){
            ps = ps.next;
            lenB++;
        }
        pl = headA;
        ps = headB;
        //让pl永远指向最长的链表，ps永远指向最短的链表
        int len = lenA - lenB;
        if(len < 0){ //说明此时pl指向的是一个短链表，所以进行调换
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        while(len != 0){ //让两个链表走到同一个起点
            pl = pl.next;
            len--;
        }
        //开始找交点
        while(pl != ps){
            pl = pl.next;
            ps = ps.next;
        } //循环退出后说明（1）要么pl==ps了，相遇了（2）要么链表走完了 pl==ps==null
        if(pl == null){ //链表走完了 pl==ps==null
            return null;
        }
        return pl; //pl==ps了，相遇了
    }

    public static void main1(String[] args) {
        SingleList list = new SingleList();
        list.createList();
        list.display();

        System.out.println(list.size());

        System.out.println(list.contains(6));

        list.addFirst(66);
        list.addLast(66);
        list.display();

        list.addIndex(0,77);
        list.display();

        list.remove(66);
        list.display();

        list.removeAllKey(77);
        list.display();
    }

    public static void main2(String[] args) {
        SingleList singleList = new SingleList();
        singleList.addLast(12);
        singleList.addLast(22);
        singleList.addLast(32);
        singleList.addLast(42);
        singleList.addLast(52);
        singleList.display();

        //eg2
        singleList.createLoop();
        System.out.println(singleList.hasCycle());

        //eg3
        ListNode ret = singleList.detectCycle();
        System.out.println(ret.val);
    }

}
